package 面试题;

import java.util.Scanner;

public class 排序链表 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Node root = new Node();
        Node tem = root;
        while (sc.hasNext()){
            Node node = new Node(sc.nextInt());
            tem.next = node;
            tem = tem.next;
        }

        if (root.next == null){
            System.out.println(-1);
            return;
        }

        Node node = sortList(root.next);
        while (node != null){
            System.out.print(node.val + " ");
            node = node.next;
        }
    }


    public static Node sortList(Node root){
        //双指针找到中间节点,空间O（1）
        Node fast = root;
        Node slow = root;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //找中间节点slow，将原来的链表分成两个链表
        Node newHead = slow;
        Node prev = root;
        while (prev.next != slow){
            prev = prev.next;
        }
        prev.next = null;


        //反转后一半链表
        Node dummyHead = null;//使用一个虚拟头节点，用来原地反转链表
        Node newRoot = recerseList(newHead, dummyHead);

        Node res = newRoot;
        Node tem = res;
        //将后一半链表和前一半链表在后一边链表上合并
        while (root != null && newRoot != null){
            newRoot = newRoot.next;
            tem.next = root;
            tem = tem.next;
            root = root.next;
            tem.next = newRoot;
            tem = tem.next;
        }

        if (root != null){
            tem.next = newRoot;
        }
        if (newRoot != null){
            tem.next = root;
        }

        return res;
    }

    //原地反转链表
    public static Node recerseList(Node root1, Node dummyHead){
        Node cur = root1;
        Node next = root1.next;
        while (cur != null){
            cur.next = dummyHead;
            dummyHead = cur;
            cur = next;
            if (cur != null){
                next = cur.next;
            }
        }
        return dummyHead;
    }

}
class Node{
    int val;
    Node next;

    public Node() {
    }

    public Node(int val) {
        this.val = val;
    }
}
